package previous.Test_0316;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //最长数对链
    //dp[i]表示：以i位置为结尾的最长数对链
    public int findLongestChain(int[][] pairs) {
        int n= pairs.length;
        Arrays.sort(pairs,(a,b) -> a[0]-b[0]);
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        int ret=1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(pairs[j][1]<pairs[i][0]){
                    dp[i]=dp[j]+1;
                }
            }
            ret=Math.max(ret,dp[i]);
        }
        return ret;
    }
    //最长定差子序列
    //dp[i]:表示以i位置为结尾最长的等差序列数
    public int longestSubsequence(int[] arr, int difference) {
          int n=arr.length;
          int[] dp=new int[n];
        HashMap<Integer,Integer> hash=new HashMap<>();
          Arrays.fill(dp,1);
          int ret=1;
        for (int a:arr) {
            hash.put(a,hash.getOrDefault(a-difference,0)+1);
            ret=Math.max(ret,hash.get(a));
        }
        return ret;
    }

}
